from numpy.matlib import repmat
import numpy as np
import matplotlib.pyplot as plt
plt.rcParams['font.sans-serif'] = ['SimHei'] # 步骤一（替换sans-serif字体）
plt.rcParams['axes.unicode_minus'] = False   # 步骤二（解决坐标轴负数的负号显示问题）

# 蚁群算法类
class AC0:
    def __init__(self):
        self.city = np.asarray([[1304, 2312], [3639, 1315], [4177, 2244], [3712, 1399],
                                [3488, 1535], [3326, 1556], [3238, 1229], [4196, 1004], [4312, 790], [4386, 570],
                                [3007, 1970], [2562, 1756], [2788, 1491], [2381, 1676], [1332, 695], [3715, 1678],
                                [3918, 2179], [4061, 2370], [3780, 2212], [3676, 2578], [4029, 2838], [4263, 2931],
                                [3429, 1908],
                                [3507, 2367], [3394, 2643], [3439, 3201], [2935, 3240], [3140, 3550], [2545, 2357],
                                [2778, 2826], [2370, 2975]])
        self.m = 100  # 蚂蚁数 200
        self.alfa = 1  # 信息度强度 1
        self.beta = 8 # 能见度强度 3
        self.p = 0.6   # 挥发度 0.6
        self.M = []  # 初始贪心算法的路径
        self.Cnn = 0
        self.W = np.zeros((31, 31))  # 距离矩阵
        self.calculate_distance()  # 初始化距离矩阵
        self.greedy_algiorith()  # 贪婪算法
        self.calculate_Cnn()  # 计算Cnn
        self.t0 = self.m / self.Cnn  # 初始化信息素
        self.T = np.full(shape=[31, 31], fill_value=self.t0)  # 信息素矩阵
        self.Already_Pose = np.zeros((self.m, 31))  # 已经过的城市
        self.Never_Pose = repmat(np.array(np.linspace(0, 30, 31)), self.m, 1)  # 未经过的城市
        self.step = 0  # 前进的步数
        self.L = np.zeros((self.m, 1))  # 最终路线距离矩阵
        self.iteration_num = 100 # 迭代次数
        self.Best = []  # 最好的结果
        self.path = []
    # 计算距离矩阵
    def calculate_distance(self):
        for i in range(len(self.city)):
            for j in range(len(self.city)):
                self.W[i, j] = np.sqrt(np.sum((self.city[i, :] - self.city[j, :]) ** 2, axis=0))

    # 对比已保存的城市列表M中是否出现过
    def traverse_M(self, f_index):
        h = 0
        for i in range(len(f_index)):
            if f_index[i] in self.M:
                h += 1
            else:
                break
        return f_index[h]

    # 贪婪算法
    def greedy_algiorith(self):
        # 用来判断选行、列的标志位
        t = 0
        # 城市号
        city_num = 0
        self.M.append(0)
        while (1):
            # 找行
            if (t == 0):
                # 从第一个点开始，获得距离降序排列索引值
                f_index = np.argsort(self.W[city_num, :])
                # 判断之前是否有选过，若选中过，索引号就+1，获得最终的索引号
                city_num = self.traverse_M(f_index)
                # 将到过的城市号保存到城市列表中
                self.M.append(city_num)
                # 切换标志位，转为列寻找
                t = 1
            # 找列
            if (t == 1):
                f_index = np.argsort(self.W[:, city_num])
                # 判断之前是否有选过，若选中过，索引号就+1
                city_num = self.traverse_M(f_index)
                # 将到过的城市号保存到城市列表中
                self.M.append(city_num)
                # 切换标志位，转为行寻找
                t = 0
            # 如果城市列表存满
            if len(self.M) == 31:
                # 退出循环
                break

    # 计算Cnn,初始化信息素矩阵
    def calculate_Cnn(self):
        for i in range(len(self.M)):
            if i == 30:
                self.Cnn += self.W[0, 30]
            else:
                self.Cnn += self.W[self.M[i], self.M[i + 1]]

    # 得到未经过的城市矩阵
    def get_NeverCity(self):
        Pose = self.Already_Pose[:, self.step]
        never_pose = np.zeros((self.m, 31 - (self.step + 1)))
        for i in range(self.m):
            city = self.Never_Pose[i, :]
            for j in range(len(city)):
                if city[j] == Pose[i]:
                    never_pose[i, :] = np.delete(self.Never_Pose[i, :], j)
                    break

        self.Never_Pose = never_pose
        return self.Never_Pose

    # 保存到已经过城市的城市矩阵中
    def save_city(self, Pose):
        for i in range(len(Pose)):
            self.Already_Pose[i, self.step] = Pose[i]

    # 轮盘算法
    def Roulette(self, M):
        Pose = []
        M_sum = np.sum(M, axis=1)
        for h in range(len(M)):
            M[h, :] = M[h, :] / M_sum[h]
        for i in range(self.m):
            m = 0
            r = np.random.rand()
            for j in range(M.shape[1]):
                m += M[i, j]
                if (m > r):
                    Pose.append(self.Never_Pose[i, j])
                    break
        # 返回索引值
        return Pose

    # 选择城市
    def select_city(self):
        A = self.Already_Pose
        B = self.Never_Pose
        # 距离矩阵
        distance = []
        # 信息素矩阵
        information_pheromone = []
        for i in range(self.m):
            for j in range(B.shape[1]):
                x = A[i, self.step].astype(int)
                y = B[i, j].astype(int)
                distance.append(self.W[x, y])
                information_pheromone.append(self.T[x, y])
        information_pheromone = np.array(information_pheromone).reshape(self.m, (31 - (self.step + 1)))
        distance = 1 / np.array(distance).reshape(self.m, (31 - (self.step + 1)))
        # 计算t * u
        P = (information_pheromone ** self.alfa) * (distance ** self.beta)
        # 将概率矩阵经过轮盘算选出一个城市
        Pose = self.Roulette(P)
        # 返回选择的城市
        return Pose

    # 计算已过城市的总距离
    def city_to_distance(self):
        for i in range(self.m):
            L = 0
            for j in range(31):
                if j == 30:
                    x1 = self.Already_Pose[i, 0].astype(int)
                    x2 = self.Already_Pose[i, 30].astype(int)
                    L += self.W[x1, x2]
                else:
                    x1 = self.Already_Pose[i, j].astype(int)
                    x2 = self.Already_Pose[i, j + 1].astype(int)
                    L += self.W[x1, x2]
            # 保存到总距离矩阵中
            self.L[i] = L

    # 保存历史最优结果
    def save_best(self):
        # 最短路径长度
        length = np.min(self.L)
        # 获得最短路径索引
        length_index = np.argmin(self.L)
        # 第一次
        if len(self.Best) == 0:
            # 获得最短路径
            city = self.Already_Pose[length_index]
            self.Best.append(length)
            self.path.append(city)
        # 后面的次数情况
        if length < self.Best[-1]:
            # 城市名
            city = self.Already_Pose[length_index]
            self.Best.append(length)
            self.path.append(city)
            print("路径更小了")
        else:
            self.Best.append(np.min(self.Best))

    # 更新信息素
    def update_information(self):
        for i in range(self.m):
            for j in range(31):
                if j == 30:
                    x = self.Already_Pose[i, 0].astype(int)
                    y = self.Already_Pose[i, 30].astype(int)
                else:
                    x = self.Already_Pose[i, j].astype(int)
                    y = self.Already_Pose[i, j + 1].astype(int)
                self.T[x, y] = (1 - self.p) * self.T[x, y] + 1 / (self.L[i])
        # 因为关于对角线对称的点上代表同一路径，所以与其转置矩阵相加
        self.T[x, y] = self.T[x, y] + self.T[y, x].T

    # 解析
    def calculate(self):
        # 一次走31步
        Pose = np.random.randint(0, 31, self.m)
        # 迭代一次后未经过的矩阵为空，所以得重新初始化一次
        self.Never_Pose = repmat(np.array(np.linspace(0, 30, 31)), self.m, 1)  # 未经过的城市
        for self.step in range(31):
            # 保存已经过的城市
            self.save_city(Pose)
            # 保存未经过的城市
            self.get_NeverCity()
            # 选择下一个城市
            Pose = self.select_city()
        # 获得距离矩阵
        self.city_to_distance()
        # 保存最优路径
        self.save_best()
        # 更新信息素
        self.update_information()

    # 迭代函数
    def iteration(self):
        for i in range(self.iteration_num):
            print('迭代次数：', i)
            self.calculate()
            print(np.min(self.Best))

        self.path = np.asarray(self.path)
        print('最优值：', np.min(self.Best))
        print('最优路径：', self.path[-1])
        print('有:',len(self.path), '条路径')

a = AC0()
a.iteration()

fig = plt.figure()
plt.xlabel('迭代次数')
plt.ylabel('历史最优值')
plt.plot(np.linspace(0, a.iteration_num, a.iteration_num), a.Best[:-1], color="black", label='最优值')

M = []
x = []
y = []

city = np.asarray(a.city)
paths = a.path[-1]
for i in range(len(paths)):
    a = paths[i].astype(int)
    M.append(city[a, :])
    if i == 30:
        M.append(city[paths[0].astype(int), :])
M = np.asarray(M)
x = M[:, 0]
y = M[:, 1]

fig = plt.figure()
plt.plot(x,y,'o')
plt.plot(x,y, linewidth=1, color='red')
plt.show()